\section{Evaluation} \label{sec:eval}
In this section, we implement \name{} and test it against a dataset from an OSNs, advogato \cite{trust::leventrust}. This dataset has been heavily studied \cite{trust::leventrust,trust::appleseed}, but rare of them, to our best knowledge, are based on time series analyzing and memory-concerned method as we do. In our experiment, \name{} create estimative trusts between agents who have no direct trust. By execute \name{} for a period, estimative trusts can compare with real trusts, which is manually specified afterwords estimate. To explain results, we also address some properties of advogato by graph analyzing. Results shows, \name is a efficient way to estimate in scalable and dynamic OSNs. 

\subsection{Setting up}
Advogato is a prototype of decentralized social network for open source developers. Each user can specify others a level of trust. Trusts in the dataset originally scales into four different levels: observer, apprentice, journeyer, and master. Among them, apprentice and journeyer and master are trusted agents.  Accordingly, we map them into scalar values, in order to caculation: observer=0, apprentice$=$0.3, journeyer$=$0.6, master$=$0.9. Additionally, in order to propagate, we presume all agents fully trust themselves. The dataset of advogato \footnote{\url{http://www.trustlet.org/wiki/Advogato_dataset}} includes daily trust relationships since the October of 2007 to March 2010.   

The next step is parsing the dataset into database server. We use Microsoft SQL server as the data repository. we implemented algorithm by user defined functions (UDFs), which are wrote in transit-sql scripts (t-sql). This choice is account for our experiment requires retrieving huge amount of data. 
  
Finally, we select a part of agents as experiment objects. \name{} aims to predict interpersonal trust accurately and agilely. However, we found only small portion (few hundreds out of 7562) of agents changed their trusts once trusts build up.  It's not suitable to test on all agents to prove agility in dynamic environment. Another reason is execution time, data of trusts between thousands of users over 3 years are exponential huge. We can only select part of them to test our model.

To prove it's accuracy, we first select a subset of agents, who are in dataset both at $t1$ and $t2$. (it's meaningless to compare if agents join in after $t1$). We also select agents who revaluate their trust more frequently as test objects. Because \name{} needs to be tested on time series data, agents who update trust regularly are more reliable to reflect their status of mind by their trusts. We select 300 agents who frequently change trusts as objects and other 700 agents by random selection. 

\begin{figure}[t]
        \begin{tabular}{p{4.2cm}p{4.2cm}}
        \subfigure[Without propagation]{\includegraphics[width=0.26\textwidth]{figures/no-long-propogation.pdf}} &
        \subfigure[With propagation]{\includegraphics[width=0.26\textwidth]{figures/long-propogation.pdf}}
        \end{tabular}
        \caption{\small The results of \name{}: compare acurracy between with and without propagation on 1000 sample nodes}
        \label{fig:comp}
\end{figure} 
\begin{figure}[t]
        \begin{tabular}{p{4.2cm}p{4.2cm}}
        \subfigure[Random selected agents]{\includegraphics[width=0.26\textwidth]{figures/stastic.pdf}} &
        \subfigure[More dynamic agents]{\includegraphics[width=0.26\textwidth]{figures/dynamic.pdf}}
        \end{tabular}
        \caption{\small The results of \name{}: compare acurracy between dynamic and stastic enviroments of 300 sample nodes}
        \label{fig:comp2}
\end{figure} 

\begin{figure}[t]
        \begin{tabular}{p{4.2cm}p{4.2cm}}
        \subfigure[10-13-2007 to 10-14-2007]{\includegraphics[width=0.247\textwidth]{figures/2007-10-11.pdf}} &
        \subfigure[01-01-2009 and 01-01-2010]{\includegraphics[width=0.25\textwidth]{figures/all.pdf}}
        \end{tabular}
        \caption{\small The results of \name{}: compare acurracy between different updating time}
        \label{fig:comp3}
\end{figure} 
\name{} will be evaluated by comparing test objects' estimated trusts at time $t1$ and materialized trust at $t2$ in original data, where $t1<t2$.  To demonstrate accuracy, we test \name{} against above 1000 agents and run a simulation on data between 01/01/2008 and 01/01/2010.To compare, we also test our method without propagation (Figure \ref{fig:comp}). 

To demonstrate agility: trusts can change swiftly in a short period of time. We select 300 most dynamic agents and 300 random agents as test data and execute between 01/01/2010 to 03/01/2010 (Figure \ref{fig:comp2}). 

Finally, we test \name{} against 1000 agents and run a simulation over two years. And compare the changes of results after 1 year's execution and 2 year's execution (Figure \ref{fig:comp3})

\subsection{Experiment}
We test \name{} in the dataset discussed above. To compare, we also test it without propagation: only subjective opinion are taken into account create trust decisions. Figure \ref{fig:comp} demonstrates cumulative distribution of difference between estimate (Jan 2008) and real trust (Jan 2010). From its results, we can find the prediction without propagation is no better than random guess. While with propagation can dramatically improve accuracy.

Secondly, we test \name in a shorter period (3 months between 01/01/2010 to 03/01/2010) on dynamic agents who reevaluate trusts frequently. To compare, we also test on randomly selected agents.
changed trusts most frequently Then random select 300 randomly. From results(Figure \ref{fig:comp2}), we first find that frequent updates can lead to swift converge from estimate value into real value. Secondly, by comparing Figure \ref{fig:comp2} (a) and Figure \ref{fig:comp2} (b), we find trusts outside of clique is useful to estimate trust. By taking into account more agents' views, better estimate trusts would be made. 

Finally, we compare the performance by updating trust for various periods, say 1 and 2 year(s). Because advogato is a fairly static community, most existing trust value will no longer change, once they are initialized. Therefore, we only test againist data from selected 300 most dynamic agents. To compare, we also present initial  trusts in Oct 2007 (see Figure \ref{fig:comp3}). We find that longer time updating will lead to more accuracy. 

\subsection{Analysis}
The experiment results generally prove our expectations. The \name achieves both accurate and agility from agent-centric aspect. 

However, there are questions left to be answer. In experiment, we found that, in advogato, over 80\% agents have 1-30 trustees, and very few exceptions who have over hundreds. Similar ``long tail'' phenomenon can be find in the number of cliques (Figure \ref{fig:comp4}). Since stasticlly trends of being dynamic and having more trustees are coincident. This feature is critical for us to explain the results of experiment. In long term propagation, the updates among different agents are various exponentially by their in-degrees. However, in short term propagation, the number cliques for each agent is more evenly, (Figure \ref{fig:comp4}-b). So for most agents who are not hubs of OSNs, short-term propagation plays the dominant effect in trust decisions. This finding also explains the deep reason of advogato's trust metric \cite{trust::leventrust}. Why limited sources of trust can spread into whole network. The sources, which is the most trusted users are always among hubs in our experiment. By first spreading long-term trust among them, then locally short-term propagate into others, a efficient spreading method is built up in the following way. Most long-term trust propagations are done by this small group of hubs. They form a backbone of information spreading. Since they are connection to most agents,  shallow propagation can be efficient without background information, such as global graph. 

This explains why two-level structure and effective extent insight of agents and allow them to estimate trust more accurately, as above discusses, clique numbers are more even for every agent. This means for most nodes, short-term trust can effectively share others' opinion, even for a small group of agents. The Figure (\ref{fig:com3}) shows the \name{} initially works no better than random guess. But it improves greatly within 1 year (dataset starts from 10-13-2007). Because for propagation of long-term trust, the average updating period is 6 month to 1 year. This update should be mostly caused by propagation of short-term trust. 

As Figure \ref{fig:comp4}-a shows, if basic trust is wisely selected. For example, a slight over zero because of altruism. Our model can help to predict trust even without running. Because we input dataset in time order, after each running, the graph of trusted agents will extent a bit. It can help to infer more unknown users as well. As Figure \ref{fig:comp3} shows, longer time results in more accurate prediction. This is contributed by two facts: first, the objective agents are selected by their dynamic level. Only highly active users are select in our experiment. The challenge is isolate them to explain the fundamental reason resulting in boost in accuracy. It's not done yet in this paper, due to lack of such information from dataset. We hope future study can fill in the gap. 

\begin{figure}[t]
     
        \subfigure[Kernel distribution of trustee numbers]{\includegraphics[width=0.50\textwidth]{figures/ksdnumberoftrust.pdf}} 
        \subfigure[clique numbers for 7562 users]{\includegraphics[width=0.50\textwidth]{figures/cliquenumber.pdf}}
        \caption{\small The long tail effects on the number of trustees and cliques}
        \label{fig:comp4}
\end{figure} 

We also noticed that trend of change is uneven, in Figure \ref{fig:comp3}(b), the accuracy of prediction increased most dramatically after running it with 1 years data. We think this is rooted in advogato's features. In advogato, most users created account around 2007, and 2008 to 2009 is the fast grow period of their connections. Therefore, the trust will be exhausted for future running. 

Another interesting result is about propagation. Since some agents play like hubs in the social network. \name{} can take advantage of this feature and guarantee those who are important in the OSNs can be updated with more accurate and objective trusts. Such that, even thought trust among others are static, we can still vary short-term trust by combine others' opinions. Due to this, the unstable trust will not be propagated. 